#ifndef _THESIS_LRU_LIST_H_
#define _THESIS_LRU_LIST_H_

#include <utility>
#include <cassert>

#include <Windows.h>

template <typename K, typename T>
class lru_list{
public:
	typedef T element_type;
	typedef K key_type;

	struct lru_item : public std::pair<K, T>{
		lru_item * next;
		lru_item * prev;
		lru_item () : next(NULL){}
	};

	class iterator {
	public:
		iterator() : cur_pos(NULL), owner(NULL){};
		iterator(lru_item * item, const lru_list * o) : cur_pos(item), owner(o){};
		iterator(const iterator & it) : cur_pos(it.cur_pos), owner(it.owner){}
		~iterator() {}

	public:

		std::pair<K, T> * operator -> (){
			return (std::pair<K, T> *)cur_pos;
		}

		// preincrement
		iterator & operator ++ () {
			owner->lock();
			assert(NULL != cur_pos);
			cur_pos = cur_pos->next;
			owner->unlock();
			return *this;
		}

		//postincrement
		iterator operator ++ (int) {
			owner->lock();
			iterator temp(*this);
			++*this;
			owner->unlock();
			return temp;
		}

		// predecrement
		iterator & operator -- () {
			owner->lock();
			assert(NULL != cur_pos);
			cur_pos = cur_pos->prev;
			owner->unlock();
			return *this;
		}

		// postdecrement
		iterator operator -- (int) {
			owner->lock();
			iterator temp(*this);
			--*this;
			owner->unlock();
			return temp;
		}

		bool operator == (const iterator & r){
			return cur_pos == r.cur_pos && owner == r.owner;
		}

		bool operator != (const iterator & r){
			return cur_pos != r.cur_pos || owner != r.owner;
		}

	private:
		lru_item * cur_pos;
		const lru_list * owner;
	};

public:
	lru_list(unsigned int s) : size(s){
		head = new lru_item;
		head->prev = NULL;
		lru_item * p = head;
		for(unsigned int i = 0 ; i < s ; i++){
			p->next = new lru_item;
			p->next->prev = p;
			p = p->next;
		}
		tail = p;

		InitializeCriticalSection(&mutex);
	}
	~lru_list(){
		EnterCriticalSection(&mutex);
		lru_item * p = head;
		while(NULL != p){
			head = p->next;
			delete p;
			p = head;			
		}
		LeaveCriticalSection(&mutex);

		DeleteCriticalSection(&mutex);
	}

public:
	bool find (const key_type & key, element_type & elem){
		lru_item * p;
		bool retval = false;
		EnterCriticalSection(&mutex);
		if(false == find_impl(key, &p)){
			retval = false;
		}else{
			elem = p->second;
			if(tail == p){
				tail = p->prev;
			}
			else{
				p->next->prev = p->prev;
			}
			p->prev->next = p->next;
			p->next = head->next;
			head->next->prev = p;
			head->next = p;
			p->prev = head;
			
			retval = true;
		}
		LeaveCriticalSection(&mutex);
		return retval;
	}

	void insert (const key_type & key, const element_type elem){
		lru_item * p = NULL;
		EnterCriticalSection(&mutex);
		if(false == find_impl(key, &p)){
			p = tail;
			tail = tail->prev;
			tail->next = NULL;
		}
		else{
			p->next->prev = p->prev;
			p->prev->next = p->next;
		}
		p->next = head->next;
		head->next->prev = p;
		p->prev = head;
		head->next = p;
		p->second = elem;
		p->first = key;
		LeaveCriticalSection(&mutex);
	}

	iterator begin() const {
		return iterator(head->next, this);
	}

	iterator end() const {
		return iterator(tail->next, this);
	}

	void lock() const {
		EnterCriticalSection(&mutex);
	}

	void unlock() const {
		EnterCriticalSection(&mutex);
	}

private:
	bool find_impl (const key_type & key, lru_item ** item) const {
		lru_item * p = head->next;
		while(NULL != p && !(key == p->first)){
			p = p->next;
		}
		if(NULL == p){
			return false;
		}
		else{
			*item = p;
			return true;
		}
	}

	lru_list (const lru_list & l) {}
	lru_list operator = (const lru_list & l) {}
private:
	unsigned int size;
	lru_item * head;
	lru_item * tail;
	mutable CRITICAL_SECTION mutex;
};

#endif /* _THESIS_LRU_LIST_H_ */
